with ada.text_io;
use ada.text_io;
package body binary_tree is

    type pathArray is array (natural range <>) of element_t;

    procedure print ( node : in tree_node ) is
    begin
	if node /= null then
	    print (node.left);
	    print_element(node.value);
	    put (" ");
	    print (node.right);
	end if;
    end print;

    procedure printPostOrder ( node : in tree_node ) is
    begin
	if node /= null then
	    printPostOrder(node.left);
	    printPostOrder(node.right);
	    print_element(node.value);
	    put (" ");
	end if;
    end printPostOrder;

    procedure printPath (paths : pathArray; pathLen : integer) is 
    begin
	for i in paths'first..pathLen loop
	    print_element (paths(i));
	    put(" ");
	end loop;
	new_line;
    end printPath;

    procedure printPaths_r ( node : in tree_node; paths : in pathArray; pathLen : in integer) is
	curLen : integer := pathLen;
	curPath : pathArray := paths;
    begin
	if node /= null then
	    curLen := curLen + 1;
	    curPath (curLen) := node.value;
	    if node.left = null and node.right = null then
		printPath (curPath, curLen);
	    else
		printPaths_r (node.left, curPath, curLen);
		printPaths_r (node.right, curPath, curLen);
	    end if;
	end if;
    end printPaths_r;

    procedure printPaths ( node : in tree_node ) is
	paths : pathArray(1..maxDepth(node));
	pathLen : integer;
    begin
	pathLen := 0;
	printPaths_r ( node, paths, pathLen );
    end printPaths;

    function newnode ( value : element_t ) return tree_node is
	node : tree_node;
    begin
	node := new tree_node_t;
	node.value := value;
	return node;
    end newnode;

    procedure mirror ( node : in tree_node ) is
	tmp : tree_node;
    begin
	if node /= null then
	    mirror (node.left);
	    mirror (node.right);
	    tmp := node.left;
	    node.left := node.right;
	    node.right := tmp;
	end if;
    end mirror;

    procedure double ( node : in out tree_node ) is
	tmp : tree_node;
    begin
	if node /= null then
	    double (node.left);
	    double (node.right);
	    tmp := node.left;
	    node.left := newnode(node.value);
	    node.left.left := tmp;
	end if;
    end double;
        
    function insert ( node : tree_node; value : in element_t ) return tree_node is
    begin
	if node = null then
	    return newnode (value);
	end if;
	if value > node.value then
	    node.right := insert (node.right, value);
	    return node;
	else
	    node.left := insert (node.left, value);
	    return node;
	end if;
    end insert;

    function lookup ( node : tree_node; value : in element_t ) return boolean is
    begin
	if node = null then
	    return false;
	end if;
	if node.value = value then
	    return true;
	elsif node.value > value then
	    return lookup (node.right, value);
	else
	    return lookup (node.left, value);
	end if;
    end lookup;

    function size ( node : tree_node ) return integer is
	length : integer;
    begin
	if node = null then
	    return 0;
	end if;
	length := 1 + size (node.left) + size (node.right);
	return length;
    end size;

    function maxDepth ( node : tree_node ) return integer is
	ldepth, rdepth : integer;
    begin
	if node = null then
	    return 0;
	end if;
	ldepth := 1 + maxDepth (node.left);
	rdepth := 1 + maxDepth (node.right);
	if ldepth > rdepth then
	    return ldepth;
	else
	    return rdepth;
	end if;
    end maxDepth;

    function minValue ( node : tree_node ) return element_t is
    begin
	if node.left = null or node = null then
	    return node.value;
	end if;
	return minValue (node.left);
    end minValue;

    function maxValue ( node : tree_node ) return element_t is
    begin
	if node.right = null or node = null then
	    return node.value;
	end if;
	return maxValue (node.right);
    end maxValue;

    function hasPathSum ( node : tree_node; sum : element_t; zero : element_t) return boolean is
	nextSum : element_t;
    begin
	nextSum := sum - node.value;
	if node.left = null and node.right = null then
	    return boolean'( nextSum = zero );
	elsif node.right = null then
	    return hasPathSum (node.left, nextSum, zero);
	elsif node.left = null then
	    return hasPathSum (node.left, nextSum, zero);
	else
	    return hasPathSum (node.left, nextSum, zero) or hasPathSum (node.right, nextSum, zero);
	end if;
    end hasPathSum;

end binary_tree;
